Heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem in a carrier

In this paper, we present heuristic algorithms for a three-dimensional loading capacitated vehicle routing problem arising in a real-world situation. In this problem, customers make requests of goods, which are packed in a sortment of boxes. The objective is to find minimum cost delivery routes for a set of identical vehicles that, departing from a depot, visit all customers only once and return to the depot. Apart of the usual 3D container loading constraints which ensure that the boxes are packed completely inside the vehicles and that the boxes do not overlap each other in each vehicle, the problem also takes into account constraints related to the vertical stability of the cargo and multi-drop situations. The algorithms are based on the combination of classical heuristics from both vehicle routing and container loading literatures, as well as two metaheuristic strategies, and their use in more elaborate procedures. Although these approaches cannot assure optimal solutions for the respective problems, they are relatively simple, fast enough to solve real instances, flexible enough to include other practical considerations, and normally assure relatively good solutions in acceptable computational times in practice. The approaches are also sufficiently generic to be embedded with algorithms other than those considered in this study, as well as they can be easily adapted to consider other practical constraints, such as the load bearing strength of the boxes, time windows and pickups and deliveries. Computational tests were performed with these methods considering instances based on the vehicle routing literature and actual customers’ orders, as well as instances based on a real-world situation of a Brazilian carrier. The results show that the heuristics are able to produce relatively good solutions for real instances with hundreds of customers and thousands of boxes.     

An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods simultaneously. The Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD) differs from the VRPSPD in that the customers may have either pickup or delivery demand. However, the solution approaches proposed for the VRPSPD can be directly applied to the VRPMPD. In this study, an adaptive local search solution approach is developed for both the VRPSPD and the VRPMPD, which hybridizes a Simulated Annealing inspired algorithm with Variable Neighborhood Descent. The algorithm uses an adaptive threshold function that makes the algorithm self-tuning. The proposed approach is tested on well-known VRPSPD and VRPMPD benchmark instances derived from the literature. The computational results indicate that the proposed algorithm is effective in solving the problems in reasonable computation time.     

ML-SOR: Message routing using multi-layer social networks in opportunistic communications

Opportunistic networks are a generalization of DTNs in which disconnections are frequent and encounter patterns between mobile devices are unpredictable. In such scenarios, message routing is a fundamental issue. Social-based routing protocols usually exploit the social information extracted from the history of encounters between mobile devices to find an appropriate message relay. Protocols based on encounter history, however, take time to build up a knowledge database from which to take routing decisions. While contact information changes constantly and it takes time to identify strong social ties, other types of ties remain rather stable and could be exploited to augment available partial contact information. In this paper, we start defining a multi-layer social network model combining the social network detected through encounters with other social networks and investigate the relationship between these social network layers in terms of node centrality, community structure, tie strength and link prediction. The purpose of this analysis is to better understand user behavior in a multi-layered complex network combining online and offline social relationships. Then, we propose a novel opportunistic routing approach ML-SOR (Multi-layer Social Network based Routing) which extracts social network information from such a model to perform routing decisions. To select an effective forwarding node, ML-SOR measures the forwarding capability of a node when compared to an encountered node in terms of node centrality, tie strength and link prediction. Trace driven simulations show that a routing metric combining social information extracted from multiple social network layers allows users to achieve good routing performance with low overhead cost.     

A resilient buffer allocation scheme in active queue management: a stochastic cooperative game theoretic approach

During the last decade, a plentiful number of active queue management schemes have been proposed, but their main objectives are simply allocating the buffer resource to all flows evenly, or protecting responsive flows from being degraded by unresponsive flows. However, the sending rates of the responsive flows can be determined diversely, and not all unresponsive flows have aggressively high sending rates. Furthermore, it is rational to reserve a portion of the buffer resource for certain privileged traffic. Grounded by these evidences, in this paper, we present a resilient active queue management algorithm, named Prior‐Core‐based Buffer Allocation considering diverse congestion control algorithms, fair‐unresponsive flows, and some privileged traffic. Our approach is based on stochastic cooperative game theory, where the payoffs yielded by cooperation are described by random variables, and the core is defined only over the distribution of these random payoffs; the core in this situation is called the prior‐core. As a result, it is shown that our buffer allocation, yielded by the prior‐core, achieves completely fair allocation for those flows whose requirement does not exceed the fair‐share regardless of the responsiveness, whereas aggressive flows are restricted according to availability of the buffer; all these are verified through ns‐2 simulation experiments. Copyright © 2014 John Wiley & Sons, Ltd.     

基于ARMA模型的双路径差异性分析

拟通过单向时延的历史记录对其未来趋势进行预测。首先,通过粗粒度和细粒度两种方式采集世界各地若干目标节点的单向时延作为原始数据;然后,结合多种预测模型的特点和原始数据的内在属性,提出一种基于ARMA模型的双路径差异性分析方法;最后选取合理的预测窗口对方法的准确性进行验证。结果表明,该预测方法是正确、合理的,与灰色预测模型相比能更有效地预测单项时延差序列。     

Nash equilibrium cooperative transmission strategy considering competition

In cooperative communications, employing the idle relay node for forwarding data can effectively improve the transmission rate and performance of the wireless networks. Therefore, various relay node selection algorithms are proposed. However, most of the existing algorithms just focus on the benefit caused by relay nodes, while ignoring the negative effect of the backoff duration time which does not exist in direct transmission, when more than one flow compete for the same relay node. To this end, considering both advantage and adverse impact caused by the relay node, we adopt the game-theoretic approach and propose a cooperative transmission strategy based on the Nash equilibrium, named the Nash Equilibrium Cooperative Transmission Strategy (NECTS). The NECTS can not only guarantee the gain of each flow, but also maximize the system performance, and improve the system throughput effectively. Simulation results show that the NECTS can take the advantage of cooperative communications. Meanwhile, it can avoid the unnecessary competition, and its performance outperforms that of the existing methods.     

基于三维胞元空间的MA双向并行路由算法

针对传统移动代理(MA)在监测无线传感器网络(WSNs)的感兴趣信息时产生的延迟较大和能耗较多问题,提出了基于三维胞元空间的MA双向并行(3D-BPMA)路由算法.3D-BPMA将MA与传统的客户/服务器(c/S)模式相结合,在胞元内利用C/S模式搜集信息,在单层胞元系统和路由器与路由器之间采用MA双向并行的策略进行传输.仿真结果表明:3D-BPMA与LCF,DSG-MIP算法相比减少了平均响应时间和网络平均能耗,提高了MA发送率.     

考虑交叉销售的O2O供应链合作广告策略研究

基于网络零售平台与制造商的合作广告实践，运用Stackelberg博弈理论研究了平台交叉销售效应及合作广告引导作用对O2O供应链合作广告决策的影响，并通过数值算例对参与合作广告计划前后渠道成员的决策变量均衡结果和利润进行对比分析，研究发现平台交叉销售效应是影响网络零售平台合作广告计划制定和实施的关键因素，只有当其达到一定水平时，制造商才拥有参与网络零售平台合作广告计划的资格；在一定条件时，合作广告计划能够实现制造商和网络零售平台利润的提升；当平台交叉销售效应较大时，网络零售平台获得的利润大于制造商。     

基于混合蚁群算法的异质车队低碳VRP研究

针对货运车辆在配送调度过程中产生大量碳排放的问题，建立模型将多种影响碳排放量的因素协同优化。模型中考虑了不同载重量的异质车队，两个节点之间有多条道路的柔性路径，以及车辆重量随卸货而减少的动态负载等因素，以碳排放量、行驶时间和行驶路程为优化目标，并加入了节点需求时间窗、根据速度变化划分路段、交接和卸货时间的约束。提出了一种混合蚁群算法，利用蚁群算法信息素强度更新方式保持群体记忆性，利用粒子群算法的快速收敛特性增加计算效率。通过随机数值算例的仿真优化与对比分析，验证了算法和模型的有效性。     

HSDN‐GRA: A hybrid software‐defined networking‐based geographic routing protocol with multi‐agent approach

We propose in this paper a Hybrid Software‐Defined Networking‐based Geographical Routing Protocol (HSDN‐GRA) with a clustering approach. It takes into account three different criteria to select the best relay to send data: (1) the contact duration between vehicles, (2) the available load of each vehicle, (3) and the log of encountered communication errors embedded in each cluster head. The multi‐criteria strategy allows the selection of the most reliable vehicles by avoiding communication problems and ensuring connection availability. Once the hybrid control plane has found out the next eligible neighbor, the data plane will be in charge of dividing and sending data. To validate our approach, HSDN‐GRA has been modeled and implemented in JADE, a multi‐agent platform, to be compared to other multi‐agent based protocols. Simulation results show that HSDN‐GRA achieves good performance with respect to the average routing overhead, the packet drop rate, and the throughput.